package hot100;


/*
 * Author：江松
 * Date：2023/4/13 10:49
 *
 *
 打家劫舍3：
 最优子结构+暴力:超时
Max(祖父节点+孙子节点的最大值，父节点最大值)

树形DP：记忆化,用哈希表存储当前节点的f，g值
设f为选择当前节点，g为不选择当前节点，当前树为根的数能偷到的最大价值
选择当前，就不能选左右子树的节点：f(o)=g(l)+g(r)+val
不选择当前，那么就可以选(不选)当前的左右子树节点：g(o)=max{f(l),g(l)}+max{f(r),g(r)}



做一个空间优化：每次可以返回一个数组结构，表示f，g
 */

import java.util.HashMap;

public class Main337 {
    public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

/*
    HashMap<TreeNode,Integer>f=new HashMap<>();
    HashMap<TreeNode,Integer>g=new HashMap<>();
    public  void dfs(TreeNode root){
        if(root==null)return;
        dfs(root.left);
        dfs(root.right);
        f.put(root,root.val+g.get(root.left)+g.get(root.right));
        g.put(root,Math.max(f.get(root.left),g.get(root.left))+Math.max(f.get(root.right),g.get(root.right)));
    }
    public int rob(TreeNode root) {
        f.put(null,0);
        g.put(null,0);
        dfs(root);
        return Math.max(f.get(root),g.get(root));
    }
    */



    //优化
    public int[] dfs(TreeNode root){
        if(root==null){
            return new int[]{0,0};
        }
        int left[]=dfs(root.left);
        int right[]=dfs(root.right);
        int selected=root.val+left[1]+right[1];
        int unSelected=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{selected,unSelected};
    }
    public int rob(TreeNode root){
        int ret[]=dfs(root);
        return Math.max(ret[0],ret[1]);
    }



 /*
    //当前根节点，能偷到最多的价值
    public int rob(TreeNode root){
        if(root==null)return 0;
        int res=root.val;
        //祖父+孙子节点
        if(root.left!=null){
            res+=rob(root.left.left)+rob(root.left.right);
        }
        if(root.right!=null){
            res+=rob(root.right.left)+rob(root.right.right);
        }
        //与父亲节点相比
        return Math.max(res,rob(root.left)+rob(root.right));
    }
    */
}
